/**
 * @file     getLeastNumbers.js
 * @brief    [剑指 Offer 40. 最小的k个数](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/)
 * @author   Zhu
 * @date     2023-06-11 21:46
 */

/**
 * 这里的queue按顺序维护了最小的k个数，顺序在题目要求中是多余的；
 * 所以可以考虑使用【堆】来代替queue来减少一些成本；
 * 因为使用大根堆，每次入堆只要保证替换掉堆顶元素即可，不必关心其他节点的顺序
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function (arr, k) {
    const queue = Array(k).fill(Infinity);
    for (const item of arr) {
        if (queue[0] > item) {
            insert(item);
        }
    }

    function insert(item) {
        let i = 1;
        while (i < k && queue[i] > item) {
            queue[i - 1] = queue[i];
            i++;
        }
        queue[i - 1] = item;
    }

    return queue;
};
